#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <omp.h>
#include <mpi.h>

//Minimum size of palindrome
#define minSzNPalindrome 3
#define ROOT 0

typedef size_t iter_t;

//If a character is invalid returns blank space otherwise returns lowercase character
char ProcessChar(char c)
{
	if(islower(c))
		return c;
	else if(isalpha(c))
		return tolower(c);
	return ' ';
}

//Removing nonalpha characters
char* Preprocess(char* buffer,size_t size)
{
	char* preProcessedStr;
	preProcessedStr=(char*)malloc(sizeof(char)*size);
	
	iter_t I;
	size_t J_ce,J_se;
	J_ce=J_se=0;

	preProcessedStr[J_ce++]=' ';

	//This flag help us in case there are a sequence of blank spaces, only one is left
	int flagSpaceFound=0;
	for(I=0;I<size;I++)
	{
		char ch=ProcessChar(buffer[I]);
		if(ch==' '&&flagSpaceFound==0)
		{
			preProcessedStr[J_ce++]=ch;
			flagSpaceFound=1;
		}
		else if(ch!=' ')
		{
			preProcessedStr[J_ce++]=ch;
			flagSpaceFound=0;
		}
	}

	preProcessedStr[J_ce]='\0';
	
	return preProcessedStr;
}

//Print string of range [i,j]
void PrintRange(char* str,iter_t i,iter_t j)
{
	char tmp=str[j];
	str[j]='\0';
	printf("%s\n",&str[i+1]);
	str[j]=tmp;
}

//This naive algorithm finds for one or more word composed palindromes on an iterator centered
void BruteForceAlgorithm(char* str,size_t size,int rank,int nProcesses)
{
	iter_t I;
	#pragma omp parallel private(I) shared(str,size,cPalindromos,rank,numProcesos)
	{
		#pragma omp for 
		//Finding palindromes between a disjoint range
		for(I=size*rank/nProcesses;I<size*(rank+1)/nProcesses;I++)
		{
			//Left and right index iterators
			iter_t l=I,r=I;

			//Finding odd palindromes
			while(l>=0&&r<=size-1)
			{
				if(str[l]==str[r])
				{
					l--;
					r++;
				}
				else if(str[l]==' ')
					l--;
				else if(str[r]==' ')
					r++;
				else
					break;
			}
		
			//Print palindrome if the palindrome range is between spaces and its size is bigger than minimum size
			if((r-l)-2>minSzNPalindrome&&str[l+1]==' '&&str[r-1]==' ')
				PrintRange(str,l+1,r-1);
			
			//Finding even palindromes
			l=I,r=I+1;
			
			//Avoids palindromes with beginning and ending spaces
			if(str[l]!=' '&&' '!=str[r])
			while(l>=0&&r<=size-1)
			{
				if(str[l]==str[r])
				{
					l--;
					r++;
				}
				else if(str[l]==' ')
					l--;
				else if(str[r]==' ')
					r++;
				else
					break;
			}
			
			//Print palindrome if the palindrome range is between spaces and its size is bigger than minimum size
			if((r-l)-2>minSzNPalindrome&&str[l+1]==' '&&str[r-1]==' ')
				PrintRange(str,l+1,r-1);
		}
	}
}

int main(int argc,char** argv)
{
	int nProcesses,rank,chunkSize;
	char* preProcessedStr=NULL;

	MPI_Init(&argc,&argv);

	MPI_Comm_size(MPI_COMM_WORLD,&nProcesses);
	MPI_Comm_rank(MPI_COMM_WORLD,&rank);

	if(rank==ROOT)
	{
		char nameFile[255];

		if(argc>1)
			sscanf(argv[1],"%s",nameFile);
		else
		{
			fprintf(stderr,"File is not set!\n");
			MPI_Finalize();
			return 1;
		}
		
		FILE* inputFile;
		inputFile=fopen(nameFile,"r");
		
		if(inputFile==NULL)
		{
			fprintf(stderr,"Error opening file!\n");
			MPI_Finalize();
			return 1;
		}
		
		char* inputBuffer;
		
		//File size
		size_t fSize;
		
		fseek(inputFile,0,SEEK_END);
		fSize=ftell(inputFile);
		rewind(inputFile);
		
		inputBuffer=(char*)malloc(sizeof(char)*fSize);
		
		size_t bytesRead;
		bytesRead=fread(inputBuffer,1,fSize,inputFile);

		if(bytesRead!=fSize)
		{
			fprintf(stderr,"Memory error!\n");
			MPI_Finalize();
			return 1;
		}
		
		//Preprocess data read from file
		preProcessedStr=Preprocess(inputBuffer,fSize);
		chunkSize=strlen(preProcessedStr);
	}
		
	//Broadcasting the size of the preprocessed string
	MPI_Bcast(&chunkSize,1,MPI_LONG,ROOT,MPI_COMM_WORLD);

	//Allocating space for receive the preprocessed string in each node
	if(rank!=ROOT)
		preProcessedStr=(char*)malloc(sizeof(char)*chunkSize);

	//Broadcasting the entire preprocessed string
	MPI_Bcast(preProcessedStr,chunkSize,MPI_CHAR,ROOT,MPI_COMM_WORLD);

	BruteForceAlgorithm(preProcessedStr,chunkSize,rank,nProcesses);

	free(preProcessedStr);

	MPI_Finalize();

	return 0;
}
